package samegame;

import java.util.ArrayList;
import java.util.List;

/**
 * Thanks for the solution.
 * @author Qu huanwen
 *
 */
public class SameGame {

	public static void main(String[] args) {
		SameGame game = new SameGame();
		System.out.println(game.getScore(new String[] { "RBB", "RRR", "RBB" },
				"RB"));

		System.out.println(game.getScore(new String[] { "ABCD", "ABCD", "ABCD",
				"ABCD" }, "ABCD"));

		System.out.println(game.getScore(new String[] { "ABCD" }, "ABCD"));
		System.out.println(game.getScore(new String[] { "ACCAA", "ABAAA",
				"ABBBA", "AAACD" }, "EABCD"));
		System.out.println(game.getScore(new String[] { "ABABABABABABABABABAB",

		"ABABABABABABABABABAB", "CDCDCDCDCDCDCDCDCDCD", "CDCDCDCDCDCDCDCDCDCD",
				"EFEFEFEFEFEFEFEFEFEF", "EFEFEFEFEFEFEFEFEFEF",
				"GHGHGHGHGHGHGHGHGHGH", "GHGHGHGHGHGHGHGHGHGH",
				"IJIJIJIJIJIJIJIJIJIJ", "IJIJIJIJIJIJIJIJIJIJ",
				"KLKLKLKLKLKLKLKLKLKL", "KLKLKLKLKLKLKLKLKLKL",
				"MNMNMNMNMNMNMNMNMNMN", "MNMNMNMNMNMNMNMNMNMN",
				"OPOPOPOPOPOPOPOPOPOP", "OPOPOPOPOPOPOPOPOPOP",
				"QRQRQRQRQRQRQRQRQRQR", "QRQRQRQRQRQRQRQRQRQR",
				"STSTSTSTSTSTSTSTSTST", "STSTSTSTSTSTSTSTSTST",
				"UVUVUVUVUVUVUVUVUVUV", "UVUVUVUVUVUVUVUVUVUV",
				"WXWXWXWXWXWXWXWXWXWX", "WXWXWXWXWXWXWXWXWXWX",
				"YZYZYZYZYZYZYZYZYZYZ", "YZYZYZYZYZYZYZYZYZYZ",
				"WXWXWXWXWXWXWXWXWXWX", "WXWXWXWXWXWXWXWXWXWX",
				"UVUVUVUVUVUVUVUVUVUV", "UVUVUVUVUVUVUVUVUVUV",
				"STSTSTSTSTSTSTSTSTST", "STSTSTSTSTSTSTSTSTST",
				"MNMNMNMNMNMNMNMNMNMN", "MNMNMNMNMNMNMNMNMNMN",
				"QRQRQRQRQRQRQRQRQRQR", "QRQRQRQRQRQRQRQRQRQR",
				"OPOPOPOPOPOPOPOPOPOP", "OPOPOPOPOPOPOPOPOPOP",
				"KLKLKLKLKLKLKLKLKLKL", "KLKLKLKLKLKLKLKLKLKL",
				"IJIJIJIJIJIJIJIJIJIJ", "IJIJIJIJIJIJIJIJIJIJ",
				"GHGHGHGHGHGHGHGHGHGH", "GHGHGHGHGHGHGHGHGHGH",
				"EFEFEFEFEFEFEFEFEFEF", "EFEFEFEFEFEFEFEFEFEF",
				"CDCDCDCDCDCDCDCDCDCD", "CDCDCDCDCDCDCDCDCDCD",
				"ABABABABABABABABABAB", "ABABABABABABABABABAB" },
				"ABCDEFGHIJKLMNOPQRSTUVWXYZ"));
	}

	private static class Pos {
		int row, col;

		public Pos(int r, int c) {
			row = r;
			col = c;
		}
	}

	private static class Group implements Comparable<Group> {
		List<Pos> blocks = new ArrayList<SameGame.Pos>();
		int topRow, leftCol;

		public void addBlock(int row, int col) {
			if (row < topRow)
				topRow = row;
			else if (row == topRow) {
				if (col < leftCol)
					leftCol = col;
			}
			blocks.add(new Pos(row, col));
		}

		@Override
		public int compareTo(Group o) {
			int size = blocks.size();
			int size2 = o.blocks.size();
			if (size > size2)
				return -1;
			else if (size < size2)
				return 1;

			if (topRow < o.topRow)
				return -1;
			else if (topRow > o.topRow)
				return 1;

			if (leftCol < o.leftCol)
				return -1;
			else if (leftCol > o.leftCol)
				return 1;

			return 0;
		}
	}

	private int rows, cols;
	private char[][] board;

	public int getScore(String[] b, String order) {
		buildBoard(b);

		int score = 0;
		int i = 0;
		while (i < order.length()) {
			Group group = findGroup(order.charAt(i));
			if (group != null) {
				score += clearGroup(group);
				if (isEmpty()) {
					return score * 4;
				}
				fallDown();
				shiftLeft();
			} else {
				i++;
			}
		}
		return score;
	}

	private void fallDown() {
		for (int col = 0; col < cols; col++) {
			for (int row = 1; row < rows; row++) {
				if (board[row][col] == '-')
					fallDown(row, col);
			}
		}
	}

	private void fallDown(int row, int col) {
		for (int row2 = row; row2 > 0; row2--) {
			board[row2][col] = board[row2 - 1][col];
		}
		board[0][col] = '-';
	}

	private boolean isEmpty() {
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (board[row][col] != '-')
					return false;
			}
		}
		return true;
	}

	private void shiftLeft() {
		for (int col = cols - 2; col >= 0; col--) {
			if (isEmptyColumn(col))
				shiftLeft(col);
		}
	}

	private void shiftLeft(int col) {
		for (int row = 0; row < rows; row++) {
			for (int col2 = col; col2 < cols - 1; col2++) {
				board[row][col2] = board[row][col2 + 1];
			}
			board[row][cols - 1] = '-';
		}
	}

	private boolean isEmptyColumn(int col) {
		for (int row = 0; row < rows; row++) {
			if (board[row][col] != '-')
				return false;
		}
		return true;
	}

	private int clearGroup(Group group) {
		for (Pos p : group.blocks) {
			board[p.row][p.col] = '-';
		}
		int n = group.blocks.size();
		return n * (n - 1) / 2;
	}

	private void buildBoard(String[] ss) {
		rows = ss.length;
		cols = ss[0].length();
		board = new char[rows][cols];
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				board[row][col] = ss[row].charAt(col);
			}
		}
	}

	private Group findGroup(char color) {
		int[][] markerBoard = new int[rows][cols];
		int marker = 1;
		Group min = null;
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (board[row][col] == color && markerBoard[row][col] == 0) {
					Group group = new Group();
					markGroup(row, col, color, marker++, markerBoard, group);
					if (min == null || group.compareTo(min) < 0)
						min = group;
				}
			}
		}
		if (min == null || min.blocks.size() < 2)
			return null;
		return min;
	}

	private void markGroup(int row, int col, char color, int marker,
			int[][] markerBoard, Group group) {
		if (row < 0 || row >= rows || col < 0 || col >= cols)
			return;
		if (board[row][col] == color && markerBoard[row][col] != marker) {
			markerBoard[row][col] = marker;
			group.addBlock(row, col);
			markGroup(row, col - 1, color, marker, markerBoard, group);
			markGroup(row, col + 1, color, marker, markerBoard, group);
			markGroup(row - 1, col, color, marker, markerBoard, group);
			markGroup(row + 1, col, color, marker, markerBoard, group);
		}
	}
}